Computer networks allow users to share or multiplex resources such as printer servers, routers, file systems, long-distance data trunks, search engine servers and web site servers. However, sharing of these resources introduces a contention problem for the shared resource. Consider, for example, a plurality of queries made to a server hosting a worldwide web search engine. Each query represents a service request from a user and contends for full access to the shared resource (i.e., the search engine) with other users accessing the search engine. Typically, the server can serve only one request at any given time so that all requests arriving while the server is busy must wait. The busy server holds the incoming search request in a service queue until it eventually selects the request for service. As more requests accumulate in the service queue, the server must use a scheduling algorithm to decide which request is served next. Generally, it is desirable for the server implement a scheduling algorithm that fairly shares the server resource.
It may also be necessary or desirable to assign a priority to the users, based either upon the class to which the user is assigned (based, for instance, on the fee paid by the user for service by the network device) or the type of data awaiting service. Generally, such priority assignments are beneficial only if there is contention for the network resource. As more users are assigned to the resource, the probability for contention increases.
Although there are many types of data carried over a network, these can be generally categorized into two data types with respect to latency and other network performance aspects that can distort the signal, or render it unusable, at the receiving end. The first data type is relatively insensitive to the network performance and is able to accept whatever performance the network provides. For example, a file transfer application ideally prefers to have an infinite bandwidth (which is generally measured in bits or bytes per second) and a zero delay as the bytes or packets traverse their intended route. Under these conditions the file will reach its destination in the fastest and most expeditious manner. However, if there is degraded network performance because, for example, the available bandwidth decreases or the end-to-end delay increases, this will not substantially affect the file transfer application. The file will still arrive at the destination, albeit later than under ideal conditions. Thus the performance requirements for such applications can adapt to the available network resources. The network only promises to deliver the application packets, without guaranteeing any particular performance bound. These are also referred to as best-efforts networks.
The second class of applications or data types requires a performance bound. For example, an application that carries voice as a 64 Kbps data stream becomes nearly unusable if the network provides less than 64 Kbps over the end-to-end link. It is also known that usable telephone conversations generally are limited to a round-trip delay of less than about 150 ms. To carry data for this telephony application, the network must guarantee a bandwidth of 64 Kbps and a round trip delay of less than 150 ms. These applications thus demand a guarantee of service quality (e.g., higher bandwidth and lower throughput delay) from the network.
To allow the co-existence of both the best efforts and guaranteed service applications or data types on a network, and reasonably fair processing of both types of packets, the network typically implements a quality of service or a grade of service scheme for processing the packets. Certain networks also implement a combination of both quality of service and grade of service criteria. The grade of service scheme provides individual subscribers with predetermined priority processing values based upon the service selected and paid for by the subscriber. Thus the subscribers paying a higher monthly fee for the resource receive a higher priority in the form of a greater bandwidth allocation. As a simple example, if a first network resource subscriber pays $100 per month for network access, it is allocated a bandwidth of 10 Kbps for the delivery of its packets. A second subscriber paying $10 per month is granted a bandwidth of 1 Kbps. Thus in any given one second interval the first subscriber is permitted to transmit 10 kilobits of data, while the second subscriber can transmit only one kilobit of data over the network resource. Once the second subscriber's assigned bandwidth is exhausted, incoming bits from the second subscriber are queued until the beginning of the next time interval. The first subscribers data bits are also queued when the allocated bandwidth has been exhausted, but because the first subscriber has a bandwidth ten times wider than the second subscriber, the first subscriber's data bits are served ten times faster than the second subscriber's.
A quality of service resource allocation scheme for assigning data priority examines the contents of the data bit streams and determines the priority based thereon. The higher priority data is transmitted through the network resource, while the lower priority data waits until bandwidth is available. Examples of high priority data include streaming audio and streaming video as well as voice over IP (VOIP), i.e., use of Internet-type packets for sending voice grade signals. In each case, the interruption of these data bits will significantly effect the quality at the receiving end. For instance, if the video stream is interrupted the data contained within the interrupted segments is lost, creating a distorted and incomplete video image at the receiving end. Comparatively, FTP data transfers or text transmitted from a web site can endure some level of interruption so long as the transmit time is not exceedingly long. Thus in this quality of service scheme the data source is not relevant to the priority assigned. Instead, the data type dictates the priority assignment.
To implement a quality of service scheme, in one embodiment a plurality of queues are formed, where each queue is populated with a specific data type. For example, one queue buffers video data and another queue buffers FTP data. To implement the quality of service scheme, the highest priority queue is always served first and typically served until the queue is empty. In this example, the highest priority queue would be the one buffering the video data. Once the video data queue is empty, the scheduler turns next to the next lower priority queue, for example audio data bits. Once the audio data queue is empty processing returns to the video queue to determine whether new video data bits have been buffered there. If none have appeared, the process jumps to the next lower priority data, and sends the bits buffered there. By continuously checking the buffering queues in order from the highest to lowest priority, the quality of service scheme is implemented.
Returning to a grade of service system, there are many known scheduling schemes for processing the data through the network shared resource. The simplest of these schemes serve the data packets on a first-come-first-served (or first-in-first-out, FIFO) basis. More complicated schemes assign weights to the data packets based on the subscriber's requested bandwidth. Several such scheduling schemes are discussed in An Engineering Approach to Computer Networking by S. Keshav, 1997, pages 209–263.
According to the prior art, one or more scheduling algorithms are typically implemented in a semiconductor device, using separate structures within the device for each of the scheduling algorithms. The router manufacturer selects the semiconductor device implementing the algorithm that it prefers, and incorporates the device in to the router such that the selected scheduling algorithm is operative.
To manufacture a semiconductor device implementing one or more scheduling algorithms, the hardware logic is designed and the design is verified. The chip layout is created and then the device is fabricated. In the event more than one scheduling algorithm is implemented in a single device, each is designed and verified individually and each occupies a separate region of the device. Thus more design and verification resources and real estate must be devoted to such a device due to the separately-implemented scheduling algorithms